/**
 * NOTE: 问题数组为什么是从 0 开始进行标记的 ????;
 *
 * 特点: 线性表, 连续的内存空间, 相同的数据类型 => [随机的访问为 O(1), 根据寻址公式直接算出地址],
 *
 * 从 0 开始;
 * arr[i] = base_addr + (i) * type_size
 *
 * 从 1 开始
 * arr[i] = base_addr + (i-1) * type_size
 *
 * 数组扩容是需要新开辟一个空间然后将数据进行迁移,
 *
 * 插入操作:
 *
 *    数组插入一个数据, 是需要数据搬移内存空间, 因为数组的内存地址是连续的, 这样数组的插入和删除的操作就是比较耗时
 * 向数组的最后面插入数据, 不需要进行数据的搬移,
 *
 * 删除操作优化:
 *
 *  标记从需要删除的元素, 将下表 0, 移动到新的起始位置, 等到了数组中位置不够的时候, 再一次性删除需要删除的元素; 类似 JVM 中垃圾回收机制
 *
 * 支持动态扩容
 *
 * 时间复杂度的
 *
 *  根据下标进行访问: O(1), 普通的查找: O(n), 有序的二分查找是: O(logn)
 *  插入: O(n) => 优化之后为 O(1)
 *  删除: O(n) => 将删除进行标记, 一次性删除
 *
 *
 */

export class ArrayList<T> {
  private data: T[]
  private count: number
  constructor(cap: number) {
    this.data = new Array(cap)
    this.count = 0// 一开始一个数都没有存所以为0
  }

  /**
   *
   */
  public insert(index: number, value: T) {
    // 位置合法, 这里数组的下标是从 0 开始; 那么实际上 count 位置是空的
    for (let i = this.count; i > index; --i) {
      this.data[i] = this.data[i - 1]
    }
    this.data[index] = value
    ++this.count
    return true
  }

  /**
   *print
   */
  public print() {
    console.log(this.data)
  }
}
